package com.mgq.algorithm.greedy;

/**
 * @author MaGuangQi
 * n皇后问题
 * @date 2022-01-06 09:58
 **/
public class NQueen {
    public static int num1(int n) {
        if (n < 0) {
            return 0 ;
        }
       int[] records= new int[n];
        return process(0, records, n);
    }

    public static void main(String[] args) {
        System.out.println(num1(3));
        System.out.println(num1(3));
        System.out.println(num1(3));
    }
    /**
     *
     * @param i 表示当前所在的行
     * @param record record[i]=? 表示i行 ?列可以摆
     * @param n 表示是几皇后
     * @return
     */
    public static int process(int i,int[] record, int n) {
        // 表示摆完了 i从0开始,到n的时候,就表示摆完了,此时是1种摆法
        if (i == n) {
            return 1;
        }
        int res=0;
        for (int j = 0; j < n; j++) {
            if (isValidate(record, i, j)) {
                record[i]=j; //每行只能放一个
                res += process(i + 1, record, n);
            }
        }
        return res;
    }

    /**
     * 验证i行j列能否放
     *就是要验证不能同列,不能共斜线
     * 只需要验证0->i-1列,因为i后面还没有摆
     * record[2]=1 表示第2行,第1列摆一个皇后
     * @param record 表示符号条件的皇后.隐含的意思是 record里面的皇后都满足条件
     * @param i 第i行
     * @param j 第j列
     * @return 能否在第i行,第j列放皇后
     */
    public static boolean isValidate(int[] record,int i,int j) {

        for (int k = 0; k < i; k++) {
            //record[k] == j 不同列
            //(Math.abs(i - k) == Math.abs(record[k] - j)) 不共斜线
            if (record[k] == j || (Math.abs(i - k) == Math.abs(record[k] - j))) {
                return false;
            }
        }
        return true;
    }
}
